Memory coherence is an issue that affects the design of computer systems in which one or more processors share a common area of memory with one or more processors or input/output (I/O) peripheral agents accessing that area of memory. A computer system does useful work, for example, by reading data from permanent storage into memory, performing some operation on that data, such as adding two numbers, and then storing the result back to permanent storage. In a uniprocessor system, there is only one processor functioning, and therefore, only one processor that can read or write data values back to permanent storage. Moreover, a simple uniprocessor may only do one thing at a time. Thus, in a uniprocessor system, when a value in memory is changed, all subsequent read operations may see the updated value.
In multiprocessor systems, or in a uniprocessor system where there are I/O agents that can independently access memory, there is the possibility that multiple processors, or a processor and an I/O agent, may need to process the same data value at the same time. Provided that the data value is not updated, copies of the data value may be shared indefinitely.
The problem of maintaining memory coherence is introduced by local caches. A cache is a collection of data that duplicates original values stored elsewhere or computed earlier, where the original data is expensive to fetch or to compute, compared to the cost of reading the cache. In other words, a cache is a temporary storage area where frequently accessed data can be stored for rapid access. For example, a processor may contain a small on-chip cache where the processor temporarily stores data for immediate use and a larger off-chip cache for storing other short-term data. Once a processor updates its local cache copy of shared data, the other processors or I/O will be working with an out-of-date copy. Thus, some scheme is required to notify all processors of changes to shared values. Such a scheme is known as a cache coherence protocol.
Cache coherency refers to the integrity of data stored in local caches of shared resources. When clients in a system maintain caches of a common memory resource, problems may arise with inconsistent data. This is particularly true of processors in a multiprocessing system. For example, if a first client has a copy of a memory block from a previous read, and a second client changes that memory block, the first client may be left with an invalid cache of memory without notification of the change. A cache coherence protocol may be implemented to manage such conflicts and maintain consistency between cache and memory. Where there are multiple levels of caches—e.g. L1, L2 etc. levels of cache—a cache coherence protocol is associated with each cache level, which may be different at each level, and there are interactions between the policies among the adjacent levels.
FIG. 1 depicts a Modified-Exclusive-Shared-Invalid (MESI) memory coherence protocol state machine 30. In the MESI coherence protocol, cache or memory lines are marked as being in one of four states: Modified, Exclusive, Shared, and Invalid. Each of these states is associated with certain rules for reading, modifying, and writing-back to memory data contained in the associated line. The MESI memory coherence protocol state machine 30 identifies the progression of line-state identifiers as different local actions are taken with respect to a data line and different actions by other entities in the shared resource network are detected or snooped. The meanings of the four MESI states are as follows: the modified state 32 means that the data in the respective line is modified from the version stored in a higher level memory, such as a higher level cache, main memory, or permanent memory; the exclusive state 34 denotes that the data copy on the respective line is held exclusively by the local resource and has not been modified (e.g. data is ‘clean’); the shared state 36 identifies that data in the associated data line is being shared by other resources; and the invalid state 38 notes that the respective data line is invalid and should not be utilized for further calculations without refreshing. The modified and exclusive states carry the right-to-modify, so that modifications can be made without any notification to a higher level cache or memory. The shared state does not carry the right-to-modify, so modification rights must be obtained from a higher level cache or memory to transition to an exclusive or modified state.
In addition to the MESI protocol, several other coherence protocols have been developed. The Modified-Shared-Invalid (MSI) memory coherence protocol is a simplified form of the MESI protocol that does not include the exclusive state. FIG. 2 depicts a Modified-Shared-Invalid (MSI) memory coherence protocol state machine 70. The MSI memory coherence protocol state machine identifies transitions among the modified state 72, the shared state 74, and the invalid state 76. Other memory coherence protocols include: the Modified-Owned-Shared-Invalid (MOSI) protocol; the Modified-Owned-Exclusive-Shared-Invalid (MOESI) protocol; the Write-once protocol; the Synapse protocol; the Berkeley protocol; the Illinois protocol; the Firefly protocol; and the Dragon protocol.